W14. Shortest Path Algorithms

Author

Nikolai Kudasov

Published

April 21, 2026

1. Theory

1.1 Shortest-Path Problem Family

1.1.1 Core Problem and Applications

Given a weighted directed graph and two vertices , the shortest-path problem asks for a path from to whose total weight is as small as possible. This is one of the central graph problems because many real systems are naturally modeled as weighted networks: packets move through routers, travelers move through cities, jobs move through dependency pipelines, and compilers move through state spaces when optimizing code.

The shortest-path weight from to is

A shortest path is any path whose weight equals . If every edge has weight , then minimizing total weight is exactly the same as minimizing the number of edges, so becomes the minimum hop count.

1.1.2 Standard Variants

The lecture distinguishes several standard shortest-path variants, and the choice of algorithm depends on which variant is required.

Single-pair shortest path: compute a shortest path from one source to one target .
Single-source shortest paths (SSSP): compute shortest paths from one fixed source to every vertex.
Single-destination shortest paths: compute shortest paths from every vertex to one fixed destination .
All-pairs shortest paths (APSP): compute shortest paths for every ordered pair .

The single-destination problem reduces to single-source by reversing every edge. In the reversed graph, shortest paths from all vertices to in the original graph become shortest paths from to all vertices.

1.2 Optimal Substructure, Negative Cycles, and Relaxation

1.2.1 Optimal Substructure

Shortest paths have the crucial property of optimal substructure. If

is a shortest path from to , then every subpath

is itself a shortest path from to . Otherwise, if some subpath were not shortest, it could be replaced by a strictly cheaper path, which would make the whole path cheaper as well. That would contradict the assumption that is shortest.

This idea is the reason both greedy algorithms and dynamic-programming algorithms work for shortest paths. Dijkstra relies on it locally, while Floyd–Warshall relies on it through a recurrence over restricted intermediate vertices.

1.2.2 Negative Edges and Negative Cycles

Negative edge weights do not by themselves make the shortest-path problem meaningless. A graph may contain negative edges and still have perfectly well-defined shortest paths. The real obstacle is a reachable negative-weight cycle.

If a path from to can enter a directed cycle whose total weight is negative, then going around that cycle one more time always makes the path cheaper. Repeating the cycle arbitrarily many times drives the total weight downward without bound, so there is no finite minimum. In that case the natural value is not a finite number at all; informally it behaves like .

So the fundamental distinction is:

negative edges without reachable negative cycles: shortest paths are still well defined;
reachable negative cycles: shortest-path weights may fail to exist as finite minima.

1.2.3 Relaxation

The three main algorithms in this lecture are all built around relaxation. In single-source problems, each vertex stores:

a distance estimate , which is an upper bound on the true distance ;
a predecessor , which records the previous vertex on the current best-known path.

The primitive operation is:

Each relaxation either improves an estimate or leaves it unchanged. The algorithms differ mainly in the order in which they perform these relaxations:

Dijkstra chooses the next vertex greedily;
Bellman–Ford repeatedly relaxes every edge;
Floyd–Warshall relaxes all ordered pairs through progressively allowed intermediate vertices.

1.3 Dijkstra’s Algorithm

1.3.1 Greedy Idea and Relation to Prim

Dijkstra’s algorithm solves the single-source shortest-path problem when all edge weights are nonnegative. It resembles Prim’s minimum-spanning-tree algorithm very closely:

both algorithms maintain a priority queue of vertices;
both repeatedly extract one vertex with minimum key;
both update neighboring vertices through decrease-key operations.

The difference lies in the meaning of the key:

in Prim, the key of is the cheapest edge connecting to the current tree;
in Dijkstra, the key of is the current best known source-to- distance estimate.

The greedy invariant is stronger in Dijkstra: once a vertex is extracted from the queue, its estimate is final:

This is correct only because all edge weights are nonnegative. Nonnegativity guarantees that any alternative path reaching later cannot be cheaper than the path that already produced the minimum extracted estimate.

1.3.2 Pseudocode Structure

The CLRS-style structure is:

Initialize all vertices with distance and predecessor NIL, except the source with distance .
Insert all vertices into a min-priority queue keyed by .
Repeatedly extract the vertex with minimum estimate.
Relax all outgoing edges of that extracted vertex.

After termination, the predecessor pointers form a shortest-path tree rooted at the source, provided all weights are nonnegative.

1.3.3 Running Time

With adjacency lists and a binary heap:

EXTRACT-MIN is performed times at each;
DECREASE-KEY is performed at most times at each;
scanning adjacency lists contributes total.

Therefore the total time is

With Fibonacci heaps:

EXTRACT-MIN costs amortized;
DECREASE-KEY costs amortized;

so the total time becomes

The lecture also emphasizes the -ary heap expression

For dense graphs with , this becomes .

1.3.4 Why Dijkstra Fails on Negative Edges

The correctness proof of Dijkstra depends on the claim that once a vertex is extracted, it can never be improved later. A negative edge destroys exactly this claim. A path discovered afterward may enter a not-yet-processed region of the graph and then return through a negative edge, creating a smaller value for a vertex that Dijkstra already finalized.

This is why the problem is not merely a technicality: with negative weights, the algorithm’s core greedy step is no longer safe.

1.4 Bellman–Ford Algorithm

1.4.1 Fundamental Observation

Any simple path in a graph with vertices uses at most edges. If shortest paths are well defined, then each shortest path can be taken simple; otherwise a repeated vertex would create a cycle that could be removed without increasing the path weight.

This means that to compute all shortest paths from a source, it is enough to ensure correctness for paths using at most edges.

1.4.2 Algorithm and Negative-Cycle Detection

Bellman–Ford implements this observation directly:

initialize all estimates;
repeat times: relax every edge in the graph;
perform one extra pass over all edges;
if any estimate still decreases, report a reachable negative cycle.

The logic is clean. After one full pass, all shortest paths using at most one edge are correct. After two passes, all shortest paths using at most two edges are correct. After passes, all shortest paths using at most edges are correct. Hence after passes, all simple shortest paths have been covered.

The extra pass is not for computing distances. It is a certificate check: if some edge still relaxes, then some path using at least edges is improving an estimate, and that can only happen because a reachable negative cycle exists.

1.4.3 Complexity and Use Cases

Each pass examines all edges once, which costs . Since there are passes, the total running time is

This is asymptotically slower than Dijkstra on nonnegative graphs, but Bellman–Ford is the correct tool when:

negative edge weights may occur;
reachable negative cycles must be detected explicitly;
a simple, uniform edge-relaxation procedure is preferable to a greedy queue discipline.

1.5 Properties of Shortest-Path Estimates

The lecture isolates several properties that appear in correctness proofs. These are worth studying because they explain why relaxation-based algorithms converge.

1.5.1 Triangle Inequality and Upper Bounds

For any edge ,

This is the triangle inequality for shortest paths: going from to directly by a shortest path cannot be worse than first going to and then taking the edge .

At the same time, relaxation algorithms preserve the upper-bound property:

at all times. Estimates may be too large, but they are never too small.

1.5.2 No-Path, Convergence, and Path Relaxation

If no path from to exists, then both the true distance and the estimate remain . This is the no-path property.

The convergence property says that if lies on a shortest path and has already become exact before we relax , then afterward also becomes exact. This follows from the triangle inequality plus the update rule.

The path-relaxation property generalizes this. If the edges of a shortest path are relaxed in the path’s order, one after another, then the destination estimate eventually becomes exact. Bellman–Ford exploits this over repeated full passes, and Dijkstra exploits it through the fact that nonnegative edges let exactness spread outward in increasing-distance order.

1.6 Floyd–Warshall Algorithm

1.6.1 All-Pairs Perspective

The all-pairs shortest-path problem asks for for every ordered pair . For this task, a matrix-based view is natural. Floyd–Warshall stores a distance matrix and improves it by dynamic programming.

Unlike Dijkstra and Bellman–Ford, which are source-centered, Floyd–Warshall is pair-centered. It asks how the best route from to changes as more and more vertices are allowed as intermediate stops.

1.6.2 Dynamic-Programming State

Number the vertices as . Define

to be the weight of the shortest path from to whose internal vertices are all chosen from .

This is the right subproblem family because shortest paths are naturally built from intermediate vertices, not from a fixed number of edges. A shortest path may have many edges, but what matters for the recurrence is whether it is allowed to pass through the pivot vertex .

1.6.3 Recurrence and Loop Order

For each stage ,

This recurrence has a direct interpretation:

either the best path from to does not use vertex as an intermediate vertex, so the old value remains best;
or the best path does use , in which case it splits into a shortest path from to and a shortest path from to , both using only vertices up to internally.

The outermost loop must be over . If or were outermost instead, then some entries would be updated using values from the wrong stage, breaking the dynamic-programming dependency structure.

1.6.4 Complexity, In-Place Updates, and Negative Cycles

The algorithm performs three nested loops over the vertices, so its running time is

The distance matrix uses

space, and storing predecessors requires another if path reconstruction is needed.

The lecture also notes two important implementation facts:

the algorithm can be implemented in place, overwriting the distance matrix entry by entry, but this requires careful reasoning about dependencies;
if the final matrix has some diagonal entry , then the graph contains a negative-weight cycle through vertex .

1.7 Choosing the Right Algorithm

For the three algorithms in this lecture, the main selection rule is:

use Dijkstra for single-source shortest paths when all edge weights are nonnegative;
use Bellman–Ford for single-source shortest paths when negative edges may appear or when reachable negative cycles must be detected;
use Floyd–Warshall when a full all-pairs distance matrix is required.

All three are built from the same conceptual core — relaxation and optimal substructure — but they organize the computation in very different ways.

2. Definitions

Shortest-path weight : The minimum total weight of a path from to , or if no such path exists.
Shortest path: A path whose total weight equals the shortest-path weight between its endpoints.
Single-source shortest paths (SSSP): The problem of computing distances from one source vertex to all vertices.
All-pairs shortest paths (APSP): The problem of computing distances for all ordered pairs of vertices.
Distance estimate : The algorithm’s current upper bound on the true shortest-path distance from the source to .
Predecessor : The previous vertex on the current best known path to .
Relaxation: The update step that replaces by when that value is smaller.
Optimal substructure: The property that every subpath of a shortest path is itself shortest.
Negative-weight edge: An edge with weight less than .
Negative-weight cycle: A directed cycle whose total edge weight is negative.
Triangle inequality: For every edge , .
Upper-bound property: During relaxation algorithms, estimates always satisfy .
No-path property: If is unreachable from the source, then remains .
Convergence property: If is exact and lies on a shortest path, then relaxing makes exact.
Path-relaxation property: Relaxing the edges of a shortest path in order eventually makes the destination estimate exact.
Dijkstra’s algorithm: A greedy single-source shortest-path algorithm correct for nonnegative edge weights.
Bellman–Ford algorithm: A single-source shortest-path algorithm that handles negative edges and detects reachable negative cycles.
Floyd–Warshall algorithm: A dynamic-programming algorithm for all-pairs shortest paths based on allowed intermediate vertices.

3. Formulas

Shortest-path definition:
Relaxation update: If , then and
Triangle inequality:
Dijkstra with binary heap:
Dijkstra with Fibonacci heap:
Dijkstra with -ary heap:
Bellman–Ford running time:
Floyd–Warshall recurrence:
Floyd–Warshall running time:
Floyd–Warshall space usage:

4. Practice

4.1. Run Dijkstra from Vertex A (Lecture 12, Task 1)

Run Dijkstra’s algorithm on the directed graph with edges

starting from vertex .

Click to see the solution

Key Concept: Dijkstra repeatedly finalizes the vertex with the smallest current estimate. Because all edge weights are nonnegative, once a vertex is extracted its estimate is final.

Initialize:

We also set every predecessor to NIL.

Step	Extracted vertex	Successful relaxations	Distances after the step
0	—	initialize only
1		via , via
2		via
3		via
4		via
5		none
6		none	final

Now check the nontrivial relaxations explicitly.

From :
From : The edge gives , which does not improve .
From :
From : The candidate value for is , which is worse than .
From : so nothing improves.

The final shortest-path distances are:

The predecessor pointers describe the shortest-path tree:

So one set of shortest paths is:

Answer: The final distances are , , , , , and , with predecessor tree edges , , , , and .

4.2. Explain Why Dijkstra Fails with Negative Edge (Lecture 12, Task 2)

Run Dijkstra’s algorithm on the lecture graph with a negative edge and explain why the algorithm can produce an incorrect result.

Click to see the solution

Key Concept: Dijkstra assumes that once a vertex leaves the priority queue, its estimate can never improve again. Negative edges break exactly that assumption.

Suppose a vertex is extracted with some estimate . Later the algorithm may discover a path

where the edge has negative weight. Even if the prefix is found only afterward, the total

may become smaller than the supposedly final value of .

At that point Dijkstra has no repair mechanism, because extracted vertices are never returned to the queue. The algorithm therefore locks in a value that may later turn out to be too large.

So the failure is not accidental. It is structural:

Dijkstra finalizes vertices permanently.
Negative edges allow later improvements to earlier vertices.
Therefore the greedy invariant is false.

This is why Dijkstra is valid only when all edge weights are nonnegative.

Answer: Dijkstra fails because a later path through the negative edge can improve a vertex that was already finalized, violating the algorithm’s core greedy invariant.

4.3. Trace Dijkstra from Vertex L on the Large Lecture Graph (Lecture 12, Task 3)

Run Dijkstra’s algorithm on the large graph from the lecture slide, starting from vertex .

Click to see the solution

Key Concept: On a large graph, Dijkstra is still the same repeated routine: extract the smallest tentative distance, relax all outgoing edges, and record each predecessor update.

The slide image does not list every edge textually, so the most reliable self-study solution from the available source is the exact procedure to apply to the original diagram.

Initialize: and every other distance is .
Insert all vertices into a min-priority queue keyed by their tentative distance.
Repeatedly:
- extract the vertex with minimum tentative distance;
- mark as finalized;
- for every outgoing edge , perform relaxation.
Continue until the queue becomes empty.

While tracing the algorithm on paper, maintain a table with:

current queue minimum,
current distances,
predecessor changes,
the set of finalized vertices.

Three correctness checks help you catch mistakes:

Extracted distances must be nondecreasing.
Every predecessor update must satisfy
The predecessor pointers at the end must form a tree rooted at .

So, even though the OCR transcript does not preserve the full edge list, the solving method is completely determined: it is the standard Dijkstra trace used in Task 4.1, only on a larger graph.

Answer: Use the same Dijkstra trace as in Task 4.1, starting from ; the exact numeric trace depends on the original slide graph, whose full edge list is not preserved in the transcript.

4.4. Run Bellman-Ford from Source (Lecture 12, Task 4)

Run Bellman–Ford on the 5-vertex lecture graph with source , using the edge set

Click to see the solution

Key Concept: After pass , all shortest paths using at most edges are correct.

Initialize:

We now perform full passes over all edges.

Pass	Distance estimates after the pass
0
1
2
3
4

Now justify the important updates.

Pass 1

Only the outgoing edges of can help, because all other vertices still have estimate :

Pass 2

Using the new value of :

Then using the new value of :

which improves the old value .

Then using the new value of :

but this particular improvement appears cleanly only after one more full pass because Bellman–Ford propagates information edge by edge according to the scan order.

Pass 3

The value of becomes exact:

No further edge can improve any estimate.

So the final shortest-path distances from are:

In the extra negative-cycle check pass, no edge relaxes further, so there is no reachable negative cycle in this graph.

Answer: The final Bellman-Ford distances from are , , , , and , and the graph has no reachable negative cycle.

4.5. Detect a Negative Cycle with Bellman-Ford (Lecture 12, Task 5)

Use Bellman–Ford to explain why the lecture’s second 5-vertex graph contains a reachable negative cycle.

Click to see the solution

Key Concept: If Bellman-Ford can still improve some estimate after passes, then some reachable walk uses a repeated vertex, and the repeated cycle must have negative total weight.

Bellman–Ford detects a reachable negative cycle by performing one extra full pass after the usual passes.

The lecture trace shows exactly the warning sign we are looking for: the distance estimates continue decreasing from one iteration to the next instead of stabilizing. In particular, the handwritten states keep improving across later passes, which means the algorithm is repeatedly finding cheaper walks.

That behavior has only one explanation:

a walk is using more than edges,
yet it is still improving the estimate,
therefore that walk must repeat a vertex,
and the repeated cycle must have negative total weight.

So the graph contains a reachable negative-weight cycle. For every vertex reachable from that cycle, the shortest-path value is not a finite minimum, because looping around the cycle one more time always produces a cheaper path.

Answer: The graph contains a reachable negative-weight cycle, because the Bellman-Ford estimates keep decreasing even after the normal passes instead of stabilizing.

4.6. Prove Why Passes Suffice (Lecture 12, Task 6)

Let be directed and assume no negative-weight cycle is reachable from the source . Explain why outer passes over all edges suffice for Bellman–Ford.

Click to see the solution

Key Concept: In the absence of reachable negative cycles, every shortest path can be chosen simple.

A simple path in a graph with vertices uses at most edges.
After one Bellman–Ford pass, all shortest paths using at most one edge are correctly represented.
After two passes, all shortest paths using at most two edges are correctly represented.
By induction, after passes, all shortest paths using at most edges are correctly represented.

Now take any vertex reachable from . Since no reachable negative cycle exists, there is a shortest path from to that is simple. Therefore it uses at most edges. After passes, Bellman–Ford has propagated exactness along all edges of that path, so .

Thus passes are sufficient for all vertices.

Answer: passes suffice because every shortest path can be taken simple, and a simple path in a graph with vertices uses at most edges.

4.7. Modify Bellman-Ford for the Bound (Lecture 12, Task 7)

Suppose every shortest path from uses at most edges, where . Describe how to modify Bellman–Ford so that it performs at most outer passes.

Click to see the solution

Key Concept: If every shortest path uses at most edges, Bellman-Ford only needs ordinary relaxation passes, plus one optional final pass for negative-cycle detection.

If every shortest path uses at most edges, then Bellman–Ford does not need to spend full passes propagating information farther than edges from the source.

The modification is:

perform at most ordinary passes over all edges;
keep a Boolean variable changed;
during each pass, set changed = true if some relaxation succeeds;
if a pass ends with changed = false, stop early because all estimates have already converged;
after the ordinary passes, do one additional pass for negative-cycle detection.

This gives at most passes total.

Why is it correct? Because after pass , Bellman–Ford is correct for all shortest paths using at most edges. By assumption, every shortest path of interest uses at most edges, so after passes all shortest distances are already correct. The extra pass is kept only to test whether some reachable negative cycle still allows an improvement.

Answer: Replace the usual outer passes by at most ordinary passes with early stopping, then keep one extra pass for negative-cycle detection, for a total of at most passes.

4.8. Run Floyd-Warshall on the 5-Vertex Graph (Lecture 12, Task 8)

Run Floyd–Warshall on the 5-vertex lecture graph. Use the vertex order .

Click to see the solution

Key Concept: Floyd-Warshall gradually enlarges the set of allowed intermediate vertices; after stage , the matrix stores shortest paths whose internal vertices come only from the first vertices in the chosen order.

We start from the initial weight matrix , where diagonal entries are , edge weights are written explicitly, and absent edges are .

Initial matrix

	A	B	C	D	E
A	0	6		7
B		0	5	8	-4
C		-2	0
D			-3	0	9
E	2		7		0

Now process vertices one by one as allowed intermediate vertices.